//dp[i][j][k]表示，考虑[0, i]个str，满足 0的个数小于等于j，1的个数小于等于k 的子集的最大长度
//如果第i个str不拿, dp[i][j][k] = dp[i - 1][j][k]
//如果第i个str拿，dp[i][j][k] = dp[i - 1][j - i0][k - i1]
// class Solution {
// public:
//     int findMaxForm(vector<string>& strs, int m, int n) {
//         int len = strs.size();
//         vector<vector<vector<int>>> dp(len + 1, vector<vector<int>>(m + 1, vector<int>(n + 1, 0)));

//         for (int i = 1; i < len + 1; ++i)
//         {
//             for (int j = 0; j < m + 1; ++j)
//             {
//                 for (int k = 0; k < n + 1; ++k)
//                 {
//                     dp[i][j][k] = dp[i - 1][j][k];
//                     int count_0 = 0, count_1 = 0;
//                     for (auto ch : strs[i - 1])
//                         ch == '0' ? ++count_0 : ++count_1;

//                     if (j - count_0 >= 0 && k - count_1 >= 0)
//                         dp[i][j][k] = max(dp[i][j][k], 1 + dp[i - 1][j - count_0][k - count_1]);
//                 }
//             }
//         }

//         return dp[len][m][n];
//     }
// };

//当i为0时，说明没有str可以选，那么子集的长度就一定是0

//空间优化
class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
        int len = strs.size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));

        for (int i = 1; i < len + 1; ++i)
        {
            int count_0 = 0, count_1 = 0;
            for (auto ch : strs[i - 1])
                ch == '0' ? ++count_0 : ++count_1;

            for (int j = m; j >= count_0; --j)
                for (int k = n; k >= count_1; --k)
                    dp[j][k] = max(dp[j][k], 1 + dp[j - count_0][k - count_1]);
        }

        return dp[m][n];
    }
};